package main

import (
	"fmt"
)

/**
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.3 MB, 在所有 Go 提交中击败了76.56%的用户
 */
var ans []string

func removeInvalidParentheses(s string) []string {

	ans = []string{}
	l, r := 0, 0
	for _, x := range s {
		if x == '(' {
			l++
		} else if x == ')' {
			if l == 0 {
				r++
			} else {
				l--
			}
		}
	}

	dfs(s, 0, "", 0, l, r)
	return ans
}

func dfs(s string, u int, path string, cnt int, l int, r int) {

	if u == len(s) {
		if cnt == 0 { ans = append(ans, path) }
		return
	}

	if s[u] != '(' && s[u] != ')' {
		dfs(s, u + 1, path + string(s[u]), cnt, l, r)
	} else if s[u] == '(' {
		k := u
		for k < len(s) && s[k] == s[u] { k++ }
		l -= k - u
		for i := k - u; i >= 0; i-- {
			if l >= 0 { dfs(s, k, path, cnt, l, r) }
			path += "("
			cnt, l = cnt + 1, l + 1
		}
	} else {
		k := u
		for k < len(s) && s[k] == s[u] { k++ }
		r -= k - u
		for i := k - u; i >= 0; i-- {
			if cnt >= 0 && r >= 0 { dfs(s, k, path, cnt, l, r) }
			path += ")"
			cnt, r = cnt - 1, r + 1
		}
	}
}

func main() {

	fmt.Println(removeInvalidParentheses("()())()"))
	fmt.Println(removeInvalidParentheses("(a)())()"))
}
